백준 2887번

오늘 풀어본 문제는 백준의 2887번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

때는 $2040$ 년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 $N$ 개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 $3$ 차원 좌표위의 한 점으로 생각하면 된다. 두 행성 $A$ $(x_A, y_A, z_A)$ 와 $B$ $(x_B, y_B, z_B)$ 를 터널로 연결할 때 드는 비용은 $\min(\vert x_A-x_B \vert, \vert y_A-y_B \vert, \vert z_A-z_B \vert)$ 이다.

민혁이는 터널을 총 $N-1$ 개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 $N$ 이 주어진다. $(1 \le N \le 100,000)$ 다음 $N$ 개 줄에는 각 행성의 $x, y, z$ 좌표가 주어진다. 좌표는 $-10^9$ 보다 크거나 같고, $10^9$ 보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

풀이과정

1번째 시도

이 문제를 해결하기 위해서 시도한 방법은 최소 신장 트리를 구하여 가중치의 합을 알아내는 것이었다. 각 행성을 정점으로 생각하고, 모든 행성간에는 서로 간선이 있다고 생각하면 그래프를 얻어낼 수 있고, 여기서 최소 신장 트리를 구해야 하는 것이다.

그런데 문제의 조건에 따르면 $N$ 이 최대 $100,000$ 까지도 될 수 있는데다가, 어떤 정점 상에 대해서도 간선이 존재할 수 있기 때문에 단순하게 모든 간선을 살펴보는 것은 시간 초과로 이어질 것이라고 생각하였다.

이 문제를 해결하기 위한 방법은, 각각 $x$, $y$, $z$ 좌표값에 대해서 정렬된 배열들로 부터 바로 다음 정점과의 간선들만을 가져와 총 $3(N-1)$ 개의 간선들만을 살펴보는 방식을 이용하기로 하였다.

그래프 구성을 완료한 후, Kruskal 알고리즘을 이용하여 최소 신장 트리의 가중치 합을 구하였다. 이 과정에서 예전에 만들어두었던 DisjointSet 을 어제에 이어 또 사용하였다. 이번에는 수정없이 그대로 사용하였고, 코드는 내 레포지토리²에서 확인할 수 있다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>
#include "disjoint_set.hpp"

using namespace std;

struct Pos {
    int num;

    int x;
    int y;
    int z;
};

struct Edge {
    int v1;
    int v2;
    int weight;

    Edge(const Pos& A, const Pos& B) : v1(A.num), v2(B.num) {
        int dx = abs(A.x - B.x);
        int dy = abs(A.y - B.y);
        int dz = abs(A.z - B.z);

        weight = min({dx, dy, dz});
    }

    bool operator>(const Edge& other) const {
        return (this->weight > other.weight);
    }
};

struct cmp_x {
    bool operator()(const Pos& A, const Pos& B) {
        return (A.x < B.x);
    }
};

struct cmp_y {
    bool operator()(const Pos& A, const Pos& B) {
        return (A.y < B.y);
    }
};

struct cmp_z {
    bool operator()(const Pos& A, const Pos& B) {
        return (A.z < B.z);
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    vector<Pos> points_x, points_y, points_z;
    vector<bool> visited(N, false);

    for (int i=0; i<N; i++) {
        int x, y, z;
        cin >> x >> y >> z;

        points_x.push_back({i, x, y, z});
        points_y.push_back({i, x, y, z});
        points_z.push_back({i, x, y, z});
    }

    sort(points_x.begin(), points_x.end(), cmp_x());
    sort(points_y.begin(), points_y.end(), cmp_y());
    sort(points_z.begin(), points_z.end(), cmp_z());

    priority_queue<Edge, vector<Edge>, greater<>> pq;
    DisjointSet diset(N);
    unsigned long long result = 0;

    for (int i=0; i<N-1; i++) {
        pq.emplace(points_x[i], points_x[i+1]);
        pq.emplace(points_y[i], points_y[i+1]);
        pq.emplace(points_z[i], points_z[i+1]);
    }

    while (!pq.empty()) {
        Edge curr = pq.top();
        pq.pop();

        if (diset.find(curr.v1) != diset.find(curr.v2)) {
            result += curr.weight;
            diset.merge(curr.v1, curr.v2);
        }
    }

    cout << result;

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

어제 문제도 그렇고 오늘 문제도 그렇고 Union-Find 를 사용해야 했다. 왜 Union-Find 를 그렇게 좋아하는 걸까? 아무래도 CLASS 5 에서 중점적으로 다루는 내용인 것 같다. 내일은 다른 걸 좀 쓰는 문제가 나왔으면 좋겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/2887
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/disjoint_set.hpp

← Previous Post Next Post →